class LRUCache {
private:
    int size;
    unordered_map<int, pair<int, list<int>::iterator>> map;
    list<int> l;
    
    void reset(int key) {
        l.splice(l.end(), l, map[key].second);
        return;
    }
    
public:
    LRUCache(int capacity) {
        size = capacity;
    }
    
    int get(int key) {
        if(map.find(key) == map.end()) return -1;
        reset(key);
        return map[key].first;
    }
    
    void put(int key, int value) {
        if(map.find(key) != map.end())
        {
            map[key].first = value;
            reset(key);
        }
        else
        {
            l.push_back(key);
            map[key] = pair<int, list<int>::iterator>(value, --l.end());
            if(l.size() > size) 
            {
                map.erase(map.find(l.front()));
                l.pop_front();
            }
        }
        return;
        
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
